/*
题目: 寻找两个正序数组的中位数
给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

算法的时间复杂度应该为 O(log (m+n)) 。

https://leetcode.cn/problems/median-of-two-sorted-arrays
 */
public class FindMedianSortedArrays {
    int n = 0;
    int m = 0;

    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        n = nums1.length;
        m = nums2.length;
        int left = (n + m + 1) / 2;
        int right = (m + n + 2) / 2;
        return (searchMid(nums1, 0, nums2, 0, left) + searchMid(nums1, 0, nums2, 0, right)) / 2.0;
    }

    //相当于寻找第 K 小的数
    private int searchMid(int[] nums1, int start1, int[] nums2, int start2, int k) {
        if (start1 >= n)    return nums2[start2 + k - 1]; //如果start1在nums1中已经越界了
        if (start2 >= m)    return nums1[start1 + k - 1]; //别忘了起点
        if (k == 1) return Math.min(nums1[start1], nums2[start2]); //如果是"第一小的数"

        int mid1 = start1 + k / 2 - 1 >= n ? Integer.MAX_VALUE : nums1[start1 + k / 2 - 1];
        int mid2 = start2 + k / 2 - 1 >= m ? Integer.MAX_VALUE : nums2[start2 + k / 2 - 1];
        if (mid1 > mid2) return searchMid(nums1, start1, nums2, start2 + k / 2, k - k / 2);
        else    return searchMid(nums1, start1 + k / 2, nums2, start2, k - k / 2);
    }
}
